We study a path-planning problem amid a set $\mathcal{O}$ of obstacles in$\mathbb{R}^2$, in which we wish to compute a short path between two pointswhile also maintaining a high clearance from $\mathcal{O}$; the clearance of apoint is its distance from a nearest obstacle in $\mathcal{O}$. Specifically,the problem asks for a path minimizing the reciprocal of the clearanceintegrated over the length of the path. We present the first polynomial-timeapproximation scheme for this problem. Let $n$ be the total number of obstaclevertices and let $\varepsilon \in (0,1]$. Our algorithm computes in time$O(\frac{n^2}{\varepsilon ^2} \log \frac{n}{\varepsilon})$ a path of total costat most $(1+\varepsilon)$ times the cost of the optimal path.
展开▼
